/**
 * @file 单调栈
 * @author snow-tyan (zziywang@163.com)
 * @brief {Life is too short to learn cpp.}
 * @version 0.1
 * @date 2021-11-09
 * 
 * @copyright Copyright (c) 2021
 * 
 * 739.每日温度
 * 496.下一个最大元素I
 * 503.下一个最大元素II
 * 42.接雨水
 * 84.柱形图中最大矩形
 * 85.最大矩形
 */

#include <iostream>
#include <stack>
#include <unordered_map>
#include <vector>
using namespace std;

template <class T>
void print(const T &t)
{
    typename T::const_iterator it = t.cbegin();
    for (; it != t.cend(); ++it) {
        cout << *it << " ";
    }
    cout << endl;
}

template <class T>
void printMp(const T &t)
{
    typename T::const_iterator it = t.cbegin();
    for (; it != t.cend(); ++it) {
        cout << "{" << it->first << ":"
             << it->second << "}" << endl;
    }
}

class Solution
{
public:
    // 739.
    vector<int> dailyTemperatures(vector<int> &temperatures)
    {
        stack<int> stk;
        vector<int> res(temperatures.size(), 0);
        for (int i = 0; i < temperatures.size(); ++i) {
            while (!stk.empty() && temperatures[i] > temperatures[stk.top()]) {
                int top = stk.top();
                stk.pop();
                res[top] = i - top;
            }
            stk.push(i);
        }
        return res;
    }
    // 42.
    int trap(vector<int> &height)
    {
        stack<int> stk;
        int cnt = 0;
        for (int i = 0; i < height.size(); ++i) {
            while (!stk.empty() && height[i] > height[stk.top()]) {
                // 想构成“低洼”，栈中至少要有2个元素，left为左，mid中，i为右
                int mid = stk.top(); // mid就是“低洼”的底部
                stk.pop();
                if (stk.empty()) {
                    break;
                }
                int left = stk.top();
                int w = i - left - 1;
                int h = min(height[i], height[left]) - height[mid];
                cnt += w * h;
            }
            stk.push(i);
        }
        return cnt;
    }
    // 496. nums1是nums2的子集，且无重复元素
    // 找出nums1中每个元素在nums2中的下一个更大元素
    vector<int> nextGreaterElement(vector<int> &nums1, vector<int> &nums2)
    {
        // 哈希 + 对nums2使用单调栈
        unordered_map<int, int> hashmp;
        stack<int> stk;
        vector<int> res(nums1.size(), -1);
        for (int i = 0; i < nums2.size(); ++i) {
            while (!stk.empty() && nums2[i] > nums2[stk.top()]) {
                int top = stk.top();
                stk.pop();
                hashmp[nums2[top]] = nums2[i];
            }
            stk.push(i);
        }
        printMp(hashmp);
        for (int i = 0; i < nums1.size(); ++i) {
            auto it = hashmp.find(nums1[i]);
            if (it != hashmp.end()) {
                res[i] = it->second;
            }
        }
        return res;
    }
    // 503. 循环数组nums，有相同元素，自己找自己下一个最大元素
    // 由于自己查自己，所以哈希表也省了
    vector<int> nextGreaterElements(vector<int> &nums)
    {
        // unordered_map<int, int> hashmp;
        stack<int> stk;
        int n = nums.size();
        vector<int> res(n, -1);
        for (int i = 0; i < 2 * n - 1; ++i) {
            while (!stk.empty() && nums[i % n] > nums[stk.top()]) {
                int top = stk.top();
                stk.pop();
                // hashmp[top] = i % n;
                res[top] = nums[i % n];
            }
            stk.push(i % n);
        }
        // for (int i = 0; i < n; ++i) {
        //     auto it = hashmp.find(i);
        //     if (it != hashmp.end()) {
        //         res[i] = nums[it->second];
        //     }
        // }
        return res;
    }

    // 84.
    int largestRectangleArea(vector<int> &heights)
    {
        // 头部插入0，省去栈的判空、heights只有一个元素的情况判断
        heights.insert(heights.begin(), 0);
        // 尾部插入0，若是递增序列，一定会弹栈
        heights.push_back(0);
        int n = heights.size();
        stack<int> stk; // 单调递增栈，和“接雨水”相反
        stk.push(0);
        int res = 0;
        for (int i = 1; i < n; ++i) {
            while (heights[i] < heights[stk.top()]) {
                int mid = stk.top();
                stk.pop();
                int left = stk.top();
                int w = i - left - 1;
                int h = heights[mid];
                res = max(res, w * h);
            }
            stk.push(i);
        }
        return res;
    }
    // 85.
    int maximalRectangle(vector<vector<char>> &matrix)
    {
        // 看图，对每一行运行84. 高度是迄此行连续1的个数
        if (matrix.empty()) {
            return 0;
        }
        int m = matrix.size(), n = matrix[0].size();
        vector<int> heights(n, 0);
        int res = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (matrix[i][j] == '1') {
                    heights[j] += 1;
                } else {
                    heights[j] = 0;
                }
            }
            // print(heights); // deepcopy 84用了哨兵
            vector<int> temp(heights.begin(), heights.end());
            res = max(res, largestRectangleArea(temp));
        }
        return res;
    }
};

Solution solve = Solution();

void test739()
{
    vector<int> nums = {73, 74, 75, 71, 69, 72, 76, 73};
    print(solve.dailyTemperatures(nums));
}

void test496()
{
    vector<int> nums1 = {4, 1, 2};
    vector<int> nums2 = {1, 3, 4, 2};
    // vector<int> nums1 = {2, 4};
    // vector<int> nums2 = {1, 2, 3, 4};
    print(solve.nextGreaterElement(nums1, nums2));
}

void test503()
{
    vector<int> nums = {1, 3, 4, 2};
    print(solve.nextGreaterElements(nums));
}

void test84()
{
    // vector<int> nums = {2, 1, 5, 6, 2, 3};
    vector<int> nums = {2, 0};
    cout << solve.largestRectangleArea(nums) << endl;
}

void test85()
{
    vector<vector<char>> matrix = {{'1', '0'}, {'1', '0'}};
    cout << solve.maximalRectangle(matrix) << endl;
}
int main()
{
    // test739();
    // test496();
    // test503();
    // test84();
    test85();
    return 0;
}